package offer2

import (
	"math"
)

/**
原题链接:
https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/

剑指offer 44.数字序列中某一位的数字
数字以0123456789101112131415…的格式序列化到一个字符序列中。
在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：
输入：n = 3
输出：3

示例 2：
输入：n = 11
输出：0

思路:
				  范围			数字个数			字符个数
bit=1 	  i=1	  1~9			9				9*1 = 9
bit=10	  i=2	  10~99			90				90*2 = 180
bit=100	  i=3	  100~999		900				900*3 = 2700
bit=1000  i=4     1000~9999		9000			9000*4 = 36000
bit=10000 i=5     ...			...				...
...

比如n=1000,
	1.可以先求出它是处于哪一个范围之内的,
	2.再定位它具体是哪一个数字
	3.再定位是该数字的哪一位

*/

func findKthNumber(k int) int {

	if k == 0 {
		return 0
	} // 如果为0，直接返回

	bit := int64(1) // 声明bit位，i=1，计数=9
	i := 1
	count := int64(9)

	for count < int64(k) { // 只要计数 < k，进行循环
		k -= int(count)
		bit *= 10
		i++
		count = bit * int64(i) * 9
	}
	num := bit + int64((k-1)/i) // 确定是在这个区间的哪个数

	// 确定在num的哪个字符
	index := (k-1)%i + 1
	res := int(num/int64(math.Pow(10, float64(i-index)))) % 10

	return res
}
